package com.liunian.test;

import java.util.Arrays;

public class ShortestPalindrome214 {

	/**
	 给定一个字符串 s，你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。

	 示例 1：
	 输入：s = "aacecaaa"
	 输出："aaacecaaa"

	 示例 2：
	 输入：s = "abcd"
	 输出："dcbabcd"
	 */

	// 方法一： 暴力 超时
	public String shortestPalindrome1(String s) {
		StringBuilder sb = new StringBuilder();
		for (int i = s.length() - 1; i > 0; i--) {
			if (isPalindrome(s, i)) break;
			sb.append(s.charAt(i));
		}
		return sb.append(s).toString();
	}

	private boolean isPalindrome(String s, int right) {
		int left = 0;
		while (left < right) {
			if (s.charAt(left) == s.charAt(right)) {
				left++;
				right--;
			} else {
				return false;
			}
		}
		return true;
	}


	// 方法二： manacher
	public String shortestPalindrome2(String s) {
		char[] chars = s.toCharArray();
		int n = s.length();
		char[] newChars = preprocess(chars, n);
		int right = 0;
		int center = 0;
		int[] res = new int[newChars.length];
		int longest = 0;
		for (int i = 1; i < newChars.length - 1; i++) {
			int i_mirror = 2 * center - i;
			if (i < right) {
				res[i] = Math.min(right - i, res[i_mirror]);
			}
			while (newChars[i + 1 + res[i]] == newChars[i - 1 - res[i]]) {
				res[i]++;
			}
			if (i + res[i] > right) {
				right = i + res[i];
				center = i;
			}
			// res数组中存的是各个位置以该位置为中心最长回文子串的半径长度
			// 所以此处找的就是以0为left的最长半径
			if (res[i] == i - 1) {
				longest = res[i];
			}
		}
		String s1 = new String(chars, longest, n - longest);
		StringBuilder sb = new StringBuilder(s1);
		return sb.reverse().append(s).toString();
	}

	private char[] preprocess(char[] chars, int n) {
		char[] newChars = new char[2 * n + 3];
		newChars[0] = '$';
		newChars[newChars.length - 1] = '^';
		newChars[newChars.length - 2] = '#';
		for (int i = 0; i < n; i++) {
			newChars[2 * i + 1] = '#';
			newChars[2 * (i + 1)] = chars[i];
		}
		return newChars;
	}

	// 方法三： kmp
	// kmp的原理解这道题：就是将字符串倒过来从头与原字符串去匹配，找到匹配上的最长长度
	public String shortestPalindrome(String s) {
		int n = s.length();
		char[] chars = s.toCharArray();
		int[] next = new int[n];
		int j = 0;
		for (int i = 1; i < n; i++) {
			while (j > 0 && chars[i] != chars[j]) {
				j = next[j - 1];
			}
			if (chars[i] == chars[j]) {
				j++;
			}
			next[i] = j;
		}
		int best = 0;
		for (int i = n - 1; i >= 0; i--) {
			while (best > 0 && chars[best] != chars[i]) {
				best = next[best - 1];
			}
			if (chars[best] == chars[i]) {
				best++;
			}
		}
		String s1 = new String(chars, best, n - best);
		StringBuilder sb = new StringBuilder(s1);
		return sb.reverse().append(s).toString();
	}

}
